Лења сегментна дрвета

Видели смо да и сегментна и Фенвикова дрвета подржавају ефикасно израчунавање статистика одређених сегмената (распона) низа и ажурирање појединачних елемената низа. Ажурирање целих сегмената низа одједном није директно подржано. Ако се оно сведе на појединачно ажурирање свих елемената унутар сегмента, добија се лоша сложеност.

Могуће је једноставно употребити Фенвиково дрво тако да се ефикасно подржи увећавање свих елемената из датог сегмента одједном, али онда се губи могућност ефикасног израчунавања збирова елемената сегмената, већ је само могуће ефикасно враћати вредности појединачних елемената полазног низа. Основна идеја је да се одржава низ разлика суседних елемената полазног низа и да се тај низ разлика чува у Фенвиковом дрвету. Увећавање свих елемената сегмената полазног низа за неку вредност \(x\), своди се на промену два елемента низа разлика, док се реконструкција елемента полазног низа на основу низа разлика своди на израчунавање збира одговарајућег префикса, што се помоћу Фенвиковог дрвета може урадити веома ефикасно. На овај начин и ажурирање целих сегмената низа одједном и очитавање појединачних елемената можемо постићи у сложености \(O(\log{n})\), што није било могуће само уз коришћење низа разлика (увећавања свих елемената неког сегмента је тада било сложености \(O(1)\), али је очитавање вредности из низа било сложености \(O(n)\)).

Ефикасно увећање свих елемената у датом сегменту за исту вредности и израчунавање збирова сегмената могуће је имплементирати помоћу одржавања два Фенвикова дрвета или помоћу тзв. сегментних дрвета са лењом пропагацијом (енгл. lazy propagation). Ове технике ћемо описати у наредном задатку.